#include<stdlib.h>
#include<stdio.h>
//int cmp(const int** x, const int** y)
//{
//    return *x[0] > *y[0];
//}
//int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes)
//{
//    qsort(intervals, intervalsSize, sizeof(int*), cmp);
//    **returnColumnSizes = 2;
//    int** ans = (int**)malloc(intervalsSize * sizeof(int*));
//    int left = 0;
//    int right = 0;
//    int num = 0;
//    while (right < intervalsSize)
//    {
//        if (intervals[left][1] >= intervals[right][0])
//        {
//            intervals[left][1] = (intervals[left][1] > intervals[right][1] ? intervals[left][1] : intervals[right][1]);
//            right++;
//        }
//        else
//        {
//            ans[num] = (int*)malloc(sizeof(int) * 2);
//            ans[num][0] = intervals[left][0];
//            ans[num][1] = intervals[left][1];
//            ++num;
//            left = right++;
//        }
//    }
//    ans[num] = (int*)malloc(sizeof(int) * 2);
//    ans[num]
//        [0] = intervals[left][0];
//    ans[num][1] = intervals[left][1];
//    ++num;
//    *returnSize = num;
//    *intervalsColSize = 2;
//    return ans;
//}

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

 /**
  * Return an array of arrays of size *returnSize.
  * The sizes of the arrays are returned as *returnColumnSizes array.
  * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
  */
int CMP(const int** a, const int** b) {
    return *a[0] > *b[0];
}


int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes) {
    // sort
    qsort(intervals, intervalsSize, sizeof(int) * 2, CMP);

    int** res = (int**)malloc(sizeof(int) * intervalsSize * 2);
    *returnColumnSizes = malloc(sizeof(int) * intervalsSize);
    for (int i = 0; i < intervalsSize; i++) {
        res[i] = (int*)malloc(sizeof(int) * 2);
    }
    res[0] = intervals[0];
    (*returnColumnSizes)[0] = 2;
    int cnt = 0;
    for (int i = 1; i < intervalsSize; i++) {
        if (intervals[i][0] <= res[cnt][1]) {
            if (intervals[i][1] > res[cnt][1]) {
                res[cnt][1] = intervals[i][1];
            }
        }
        else {
            cnt++;
            res[cnt] = intervals[i];
        }
        (*returnColumnSizes)[cnt] = 2;
    }
    // go through all the element and get  array
    *returnSize = cnt + 1;
    return res;
}



int main()
{
    int arr[4][2] = { {1,3},{2,6},{8,10},{15,18} };
    int** str = NULL;
    int k = 4;
    int* z = NULL;
    int* s = NULL;
    int** b1 = NULL;
    str = merge(arr, 4, z, s, b1);
    return 0;
}

#include<stdlib.h>
void rotate(int** matrix, int matrixSize, int* matrixColSize)
{
    int i = 0;
    int j = 0;
    for (i = 0; i < matrixSize; i++)
        for (j = 0; j < matrixSize - i - 1; j++)
            swap(matrix[i][j], matrix[abs(matrixSize - 1 - i)][abs(matrixSize - 1 - j)]);
    for (i = 0; i < 2 / matrixSize; i++)
        for (j = 0; j < matrixSize; j++)
            swap(matrix[i][j], matrix[matrixSize - i - 1][j]);
}

int* printNumbers(int n, int* returnSize)
{
    int i = 0;
    int num = 0;
    for (; i < n; i++)
        num = 10 * num + 9;
    int* arr = (int*)malloc(num * sizeof(int));
    *returnSize = num;
    for (i = 1; i <= num; i++)
        arr[i - 1] = i;
    return arr;
}

